package com.eu.chipin.backend;
import java.util.LinkedList;
import java.util.List;


public class SubSum {
	
	public static Boolean[] getMinSubSum(Double[] data, double amount)
	{
		 
		List<Boolean[]> result = new LinkedList<Boolean[]>();
		
		getMaxSum(data, amount, 0, result, new Boolean[data.length]);
		
		if(result.size() == 0)
          return null;
		
	    int minResult = 0;
	    int minTrue = Integer.MAX_VALUE;
		for(int index = 0; index < result.size(); index++)
		{
			int totalTrue = 0;
			for(Boolean b : result.get(index))
			{
				if(b)
				{
					totalTrue++;
				}
			}
			if(totalTrue < minTrue)
			{
				minTrue = totalTrue;
				minResult = index;
			}
		}
		
		return result.get(minResult);
		
	}
	public static void getMaxSum(Double[] data, double amountLeft, int currIndex, List<Boolean[]> result, Boolean[] taken)
	{
		for(int index = currIndex; index < data.length; index++)
		{ 
			if(amountLeft == 0)
			{
	        	result.add(taken.clone());
	        	return;
			}
			
		  if(data[index] > 0 && (amountLeft - data[index] >= 0))
		  {
			 getMaxSum(data, amountLeft, index+1, result, taken.clone());
		     taken[index] = true;
		     amountLeft -= data[index];
		     
		  }
		}
	}
}
